package io.github.hadyang.leetcode.offer;

import java.util.Arrays;
import org.junit.Test;

/** @author haoyang.shi */
public class FindNumsAppearOnce {

  @Test
  public void test() {
    int[] num1 = {0};
    int[] num2 = {0};
    FindNumsAppearOnce(new int[] {2, 4, 3, 6, 3, 2, 5, 5}, num1, num2);

    System.out.println(Arrays.toString(num1));
    System.out.println(Arrays.toString(num2));

    FindNumsAppearOnce(new int[] {1, 1, 3, 6}, num1, num2);

    System.out.println(Arrays.toString(num1));
    System.out.println(Arrays.toString(num2));
  }

  /**
   * num1,num2分别为长度为1的数组。传出参数。将num1[0],num2[0]设置为返回结果
   *
   * @param array
   * @param num1
   * @param num2
   */
  public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
    if (array == null || array.length < 3) {
      return;
    }

    int result = array[0];

    for (int i = 1; i < array.length; i++) {
      result ^= array[i];
    }

    // 找到第一个为1的位
    int indexOfFirstBit1 = 0;
    int temp = result;
    while (temp != 0) {
      indexOfFirstBit1++;
      temp >>>= 1;
    }

    int mask = 1;
    for (int i = 1; i < indexOfFirstBit1; i++) {
      mask <<= 1;
    }

    // 将第一位为1的位是否为1作为分组条件，分组异或
    int n1 = -1, n2 = -1;
    for (int i : array) {
      if ((i & mask) == mask) {
        if (n1 == -1) n1 = i;
        else n1 ^= i;
      } else {
        if (n2 == -1) n2 = i;
        else n2 ^= i;
      }
    }

    num1[0] = n1;
    num2[0] = n2;
  }
}
